﻿#region using statements

using System;

#endregion

namespace NGen.Collections
{
	/// <summary>
	/// 	<para>Heap data structure.</para>
	/// 	<para>Template parameter must implement interface IComparable</para>
	/// </summary>
	/// <typeparam name = "T">heap object type</typeparam>
	public class Heap<T>
		where T : IComparable<T>
	{
		/// <summary>
		/// 	array containing all the values in the heap
		/// </summary>
		protected T[] m_heapContents;

		/// <summary>
		/// 	Construct a new heap
		/// </summary>
		public Heap() {
			m_heapContents = new T[16];
			Count = 0;
		}

		/// <summary>
		/// 	Get the number of objects stored in the heap
		/// </summary>
		public int Count { get; protected set; }

		/// <summary>
		/// 	Gets a list of the objects in the heap, in no specific order
		/// </summary>
		public T[] GetContents {
			get {
				T[] returnVal;
				lock(m_heapContents.SyncRoot) {
					returnVal = new T[Count];
					Array.Copy(m_heapContents, 1, returnVal, 0, Count);
				}
				return returnVal;
			}
		}

		/// <summary>
		/// 	Clears the heap of all data
		/// </summary>
		public void Clear() {
			lock(m_heapContents.SyncRoot) {
				m_heapContents = new T[16];
				Count = 0;
			}
		}

		/// <summary>
		/// 	Return the root item in the heap without removing it from the heap
		/// </summary>
		/// <returns>the root value in the heap</returns>
		public T Peek() {
			lock(m_heapContents.SyncRoot) {
				if(Count == 0) {
					throw new Exception("no items in the heap");
				}
				return m_heapContents[1];
			}
		}

		/// <summary>
		/// 	doubles the size of the array containing the heap data
		/// </summary>
		private void _GrowHeap() {
			var newHeap = new T[Count * 2];
			Array.Copy(m_heapContents, 1, newHeap, 1, Count - 1);
			m_heapContents = newHeap;
		}

		/// <summary>
		/// 	Add an object to the heap
		/// </summary>
		/// <param name = "p_value">the item to be added to the heap</param>
		public void Push(T p_value) {
			lock(m_heapContents.SyncRoot) {
				if(++Count ==
				   m_heapContents.Length) {
					_GrowHeap();
				}

				m_heapContents[Count] = p_value;
				_PercolateUp();
			}
		}

		/// <summary>
		/// 	Remove and return the root item from the heap
		/// </summary>
		/// <returns>the root item</returns>
		/// <exception cref = "InvalidOperationException">
		/// 	Thrown when the heap is empty
		/// </exception>
		public T Pop() {
			T returnValue;
			lock(m_heapContents.SyncRoot) {
				if(Count == 0) {
					throw new InvalidOperationException("Heap is empty");
				}

				returnValue = m_heapContents[1];
				Count--;
				if(Count >= 1) {
					m_heapContents[1] = m_heapContents[Count + 1];
					_PercolateDown();
				}
			}
			return returnValue;
		}

		/// <summary>
		/// 	Restores the heap-order property going up the tree, towards the root node
		/// </summary>
		protected void _PercolateUp() {
			var currentIndex = Count;

			//while there is a parent to the current node and the child is larger than the parent
			while((currentIndex != 1) &&
			      (m_heapContents[currentIndex >> 1].CompareTo(m_heapContents[currentIndex]) == 1)) {
				//swap the parent and child
				m_heapContents[0] = m_heapContents[currentIndex >> 1];
				m_heapContents[currentIndex >> 1] = m_heapContents[currentIndex];
				m_heapContents[currentIndex] = m_heapContents[0];

				//go up one level to next parent index
				currentIndex = currentIndex >> 1;
			}
		}

		/// <summary>
		/// 	Restores the heap-order property going down the tree, away from the root node
		/// </summary>
		protected void _PercolateDown() {
			var currentIndex = 1;

			while(_IsLeftChildSmaller(currentIndex) ||
			      _IsRightChildSmaller(currentIndex)) {
				int childIndex;
				if(!_CompareLeftChildToRight(currentIndex)) {
					childIndex = (currentIndex << 1) + 1;
				} else {
					childIndex = currentIndex << 1;
				}

				m_heapContents[0] = m_heapContents[childIndex];
				m_heapContents[childIndex] = m_heapContents[currentIndex];
				m_heapContents[currentIndex] = m_heapContents[0];
				currentIndex = childIndex;
			}
		}

		/// <summary>
		/// 	Returns whether the left child is smaller than the parent or false if this node
		/// 	is a leaf node
		/// </summary>
		/// <param name = "p_parentIndex">the parent index to test</param>
		/// <returns>true if the left child is smaller than the parent, false otherwise</returns>
		protected bool _IsLeftChildSmaller(int p_parentIndex) {
			if((p_parentIndex << 1) >=
			   Count - 1) {
				return false;
			}
			return m_heapContents[p_parentIndex << 1].CompareTo(m_heapContents[p_parentIndex]) < 0;
		}

		/// <summary>
		/// 	Returns whether the right child is smaller than the parent or false if this node
		/// 	is a leaf node
		/// </summary>
		/// <param name = "p_parentIndex">the parent index to test</param>
		/// <returns>true if the right child is smaller than the parent, false otherwise</returns>
		protected bool _IsRightChildSmaller(int p_parentIndex) {
			if((p_parentIndex << 1) + 1 >=
			   Count - 1) {
				return false;
			}
			return m_heapContents[(p_parentIndex << 1) + 1].CompareTo(m_heapContents[p_parentIndex]) < 0;
		}

		/// <summary>
		/// 	<para>Compares the child nodes</para>
		/// </summary>
		/// <param name = "p_parentIndex">index of the parent to test</param>
		/// <returns>true if the left child is smaller or they are equal,
		/// 	false otherwise</returns>
		protected bool _CompareLeftChildToRight(int p_parentIndex) {
			//both children are bigger or parentIndex is a leaf node
			if(_IsLeftChildSmaller(p_parentIndex) &&
			   _IsRightChildSmaller(p_parentIndex)) {
				//find which child is smaller
				return m_heapContents[p_parentIndex << 1].CompareTo(m_heapContents[(p_parentIndex << 1) + 1]) <= 0;
			}
			return _IsLeftChildSmaller(p_parentIndex);
		}
	}
}